package com.chaosj.algorithm

import java.util.stream.Stream

class ThreeSum {
    /**
     * 给定一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？找出所有满足条件且不重复的三元组。
     *
     * 注意：答案中不可以包含重复的三元组。
     *
     * 例如, 给定数组 nums = [-1, 0, 1, 2, -1, -4]，
     *
     * 满足要求的三元组集合为：
     * [
     *   [-1, 0, 1],
     *   [-1, -1, 2]
     * ]
     *
     * 来源：力扣（LeetCode）
     * 链接：https://leetcode-cn.com/problems/3sum
     * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。给定一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？找出所有满足条件且不重复的三元组。
     *
     * 注意：答案中不可以包含重复的三元组。
     *
     * 例如, 给定数组 nums = [-1, 0, 1, 2, -1, -4]，
     *
     * 满足要求的三元组集合为：
     * [
     *   [-1, 0, 1],
     *   [-1, -1, 2]
     * ]
     *
     * 来源：力扣（LeetCode）
     * 链接：https://leetcode-cn.com/problems/3sum
     * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
     * @param args
     */
    static void main(String[] args){
        def nums = Arrays.asList(-1,0,1,2,-1,-4).toArray(new int[6])
        System.err.println(solution(nums))
    }

    static List<List<Integer>> solution(int[] nums){
        def result = new ArrayList<>()
        Arrays.sort(nums)
        if( nums[nums.length-1]<0 || nums[0]>0 ){
            result
        }
        for (int i = 0; i < nums.length - 2; i++) {
            if( nums[i]>0 ){
                break
            }
            def left = i+1
            def right = nums.length - 1
            if( i > 0 && nums[i]==nums[i-1] ){
                continue
            }
            while (left<right){
                def sum = nums[left]+nums[right]+nums[i]
                if( sum == 0 ){
                    result.add(Arrays.asList(nums[left],nums[i],nums[right]))
                    while(left<right && nums[left]==nums[++left]){}
                    while(right>left && nums[right]==nums[--right]){}
                }else if( sum > 0 ){
                    right--
                }else{
                    left++
                }
            }
        }
        result
    }
}
